//============================================================================
// Name        : Prisons_map.h
// Author      : Andrey Bicalho Santos e Clayson Sandro Celes
// Version     :
// Copyright   : Your copyright notice
// Description : Genetic Algorithm in C++, Ansi-style
//============================================================================

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <stack>
#include "CImg.h"
#include "Individual.h"

#define PENALTY 1
#define BONUS 1
#define TAM_MIN 2
#define SLEEP_TIME 100

#define TAM_MAX_LINHA 1024

using namespace std;
using namespace cimg_library;

void pera(string s){
	cout << "\n" << s << "\n";
	string x;
	cin >> x;
}


void pera(){
	printf("\nOi!\n");
	string x;
	cin >> x;
}

typedef struct{
	int x,y;
}Point;

string *load_map(FILE *fl, int *num_linhas_mapa);
int count_lines(FILE *fl);
int **get_reduced_map(int **mapa,Point dim_map,Point *dim_reduced_map);
int **preProcessing(int **mapa,Point dim_map);
int **copy_map(int **map,Point dim_map);
void clone(int **origem,int **destino,Point dim_map);
int **str_map2bin_map(string map[], int num_linhas,Point *dim_labirinto);
int get_number_of_valid_space(int **map, Point dim_map);
void printMapa(int **map,Point dim_map);
Point FindStartPoint(int **map,Point dim_map);
Point FindEndPoint(int **map,Point dim_map);
int count_good_genes(int **solution_map,int **map,Point dim_map);
int count_erros(int **solution_map,int **map,Point dim_map);


int **InsertSolution(Individual *ind,int k,int **map,int dimx, int dimy,Point dim_map);
double euclidian_distance_2D(Point ponto1,Point ponto2);
CImg<int> update_display(int **map,CImg<int> cimg_labirinto);


bool is_wall(int **map,int x, int y);
bool is_wall_(int **map,Point current_position);
bool is_start(int **map,int x, int y);
bool is_end(int **map,int x, int y);
bool is_end_(Point end,Point current_position);
bool is_in(Point current_point, Point dim_map);
bool is_inside(int x,int y,Point dim_map);
bool check_north(Point cp,int **map,Point dim);
bool check_south(Point cp,int **map,Point dim);
bool check_east(Point cp,int **map,Point dim);
bool check_west(Point cp,int **map,Point dim);
Point *build_memory(stack<Point> mystack);
bool check_visited_place(Point *places_keeped,int path_size,Point current_position);
int check_unvisited_neighborhood(Point current_point,Point dim_map,Point *path,int path_size,int **map);



int get_index_out_point(Point *path,int num,Point dim_map);
void print_path(Point *path,int num);
Point *build_path_(stack<Point> path);
int **InsertPath(Individual *ind,int k,int **map);
int check_gene_way(int g1,int g2);
stack<Point> build_path(Individual *ind,int k,Point start);
int go_rand(void);
Point go(int **map,Point dim,Point current_position,int choice);

//---------------------------------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------------------------------
int get_index_out_point(Point *path,int num,Point dim_map){

	for(int i=0;i<num;i++){
		if(!is_in(path[i],dim_map)){
			return i;

		}
	}

	return 0;
}
//---------------------------------------------------------------------------------------------------------------------------
void print_path(Point *path,int num){

	int count = 0;
	for(int i=num-1;i>=0;i--){
		printf("\nStep %d: (%d,%d)",count,path[i].x,path[i].y);
		count++;
	}

	printf("\n");
}
//---------------------------------------------------------------------------------------------------------------------------
Point *build_path_(stack<Point> path){
	int pop_count = 0;

	Point *mypath;
	mypath = new Point[path.size()];

	int i = 0;
	while(!path.empty()){
		mypath[i] = path.top();
		i++;
		path.pop();
		pop_count++;
	}

	//reempilhando
	for(i=pop_count-1;i>=0;i--){
			path.push(mypath[i]);
	}


	return mypath;
}
//---------------------------------------------------------------------------------------------------------------------------
int **InsertPath(Individual *ind,int k,int **map,Point start){
	stack<Point> path = build_path(ind,k,start);

	while(!path.empty()){
		map[path.top().x][path.top().y] = 4;
		path.pop();
	}

	return map;
}
//---------------------------------------------------------------------------------------------------------------------------
int check_gene_way(int g1,int g2){

	if(g1 == 1 && g2 == 1) //norte
		return 0;
	else if(g1 == 0 && g2 == 0) //sul
		return 1;
	else if(g1 == 0 && g2 == 1) //leste
		return 2;
	else if(g1 == 1 && g2 == 0) //oeste
		return 3;

	return 4;
}
//---------------------------------------------------------------------------------------------------------------------------
stack<Point> build_path(Individual *ind,int k,Point start){
	int g1 =0, g2 = 0;

	stack<Point> path;
	int way = 4;
	Point current_position = start;
	path.push(current_position);
	for(int i=0;i<ind[k].getNumGenes()-1;i=i+2){
		g1 = ind[k].getGene(i);
		g2 = ind[k].getGene(i+1);

		way = check_gene_way(g1,g2);
		if(way == 0){ //norte
			current_position.x--;
		}
		else if(way == 1){ //sul
			current_position.x++;
		}
		else if(way == 2){ //leste
			current_position.y++;
		}
		else if(way == 3){ //oeste
			current_position.y--;
		}
		else{
			cout << "\nGenes loucos! stack<Point> build_path(Individual*,int,Point,Point)\n";
		}

		path.push(current_position);
	}

	return path;
}
//---------------------------------------------------------------------------------------------------------------------------
/*
 * direcoes:
 * 0 - norte
 * 1 - sul
 * 2 - leste
 * 3 - oeste
 * */
int go_rand(){

	switch(rand() % 4){
	case 0: //norte
		return 0;
	break;
	case 1: //sul
		return 1;
		break;
	case 2://leste
		return 2;
	case 3: //oeste
		return 3;
		break;
	default:
		break;
	}

	return 4;
}
//---------------------------------------------------------------------------------------------------------------------------
Point go(int **map,Point dim,Point current_position,int choice){
	//alterando a posicao corrente....
	if (choice == 0) {//go north
		if (check_north(current_position, map, dim)) {
			current_position.x--;
			//cout << "\nNorte\n";
		}
	} else if (choice == 1) { //go south
		if (check_south(current_position, map, dim)) {
			current_position.x++;
			//cout << "\nSul\n";
		}
	} else if (choice == 2) { //go east
		if (check_east(current_position, map, dim)) {
			current_position.y++;
			//cout << "\nLeste\n";
		}
	} else if (choice == 3) {//go west
		if (check_west(current_position, map, dim)) {
			current_position.y--;
			//cout << "\nOeste\n";
		}
	}

	return current_position;

}
//---------------------------------------------------------------------------------------------------------------------------
double fitness_MazeProblem(Individual *ind,int k,int n_ind,int **map,int **labirinto,Point start,Point end,Point dim_map,int free_space){
	/*
	 * direcoes:
	 * 0 - norte
	 * 1 - sul
	 * 2 - leste
	 * 3 - oeste
	 *
	 *
	 * */
	//printf("\nInicio Fitness\n");
	int n=0;
    //printf("\nIndividuo: %d\n",k);
	//gerando caminho
	double fit = 0.0000000000;
	Point current_position;
	stack<Point> path = build_path(ind,k,start);
	current_position = path.top();

    //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	//destroi caminho que leve para fora do mapa
	int i_path_size = path.size();

	//busca por caminho invalido
	Point *initialpath;
	initialpath = build_path_(path);

	//print_path(initialpath,i_path_size);
	//pera("path inicial");

	int cut_index = get_index_out_point(initialpath,i_path_size,dim_map);
	if(cut_index != 0){
		if(ind[k].getNumGenes()-(cut_index*2) > TAM_MIN){
			ind[k].DecreaseIndividual(cut_index*2);
			if (initialpath) delete[] initialpath;
			return 0;
		}
		else{
			//cout << "\nindex: " << cut_index << " ---> " << initialpath[cut_index].x << "," << initialpath[cut_index].y << "\n";
			//pera("point fora do mapa ... mas nao sera deletado");
		}
	}
	if (initialpath) delete[] initialpath;
	//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

	/*int d_size = 1;
	//Increasing Individual chromossome
	if(is_in(current_position,dim_map) && !is_end_(end,current_position)){ //dentro do mapa
		//printf("\nPosicao corrente: (%d,%d)\n",current_position.x,current_position.y);
		ind[k].IncreaseIndividual(2);
		path = build_path(ind,k,start);
		current_position = path.top();
		//printf("\nNova posicao: (%d,%d)\n",current_position.x,current_position.y);
		while(!is_in(current_position,dim_map) || is_wall_(map,current_position)){ //garantindo que crie posicao valida
			if (ind[k].getNumGenes() > TAM_MIN*d_size) {
				ind[k].DecreaseIndividual(2 * d_size);
				path.pop();
				//ind[k].IncreaseIndividual(2);
				//path = build_path(ind, k, start);
				current_position = path.top();
			}
			else{
				if (ind[k].getNumGenes() > TAM_MIN) {
					ind[k].DecreaseIndividual(2);
					path.pop();
					//ind[k].IncreaseIndividual(2);
					//path = build_path(ind, k, start);
					current_position = path.top();
				}

			}
			//printf("\nPosicao recriada: (%d,%d)\n",current_position.x,current_position.y);
			//oo loop esta aqui
			//o problema esta ocorrendo pq as 4 opcoes de criacao de posicao
			//nao atendem as condicoes triviais... sendo assim, e necessario dar
			//um decrease maior nesses casos, para ele escapar dessa "armadilha"
			d_size++;
			cout << "\n1 " << n++;
		}

	}
	else if(!is_in(current_position,dim_map)){ //fora do mapa
		if(ind[k].getNumGenes() > TAM_MIN){
			ind[k].DecreaseIndividual(2);
		}

		return 0;
	}*/


	path = build_path(ind,k,start);
	current_position = path.top();

	//Increasing Individual
	if(!is_wall_(map,current_position) && !is_end_(end,current_position)){
		ind[k].IncreaseIndividual(2);
		path = build_path(ind,k,start);
		current_position = path.top();
	}

	//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	//verificando posicoes visitadas
	Point *memory;
	memory = build_memory(path);
	int memory_size = path.size(),retorno = 0;
	if(check_visited_place(memory,memory_size,current_position) && !is_end_(end,current_position)){ //verifica se a posicao corrente foi visitada
		retorno = check_unvisited_neighborhood(current_position,dim_map,memory,memory_size,map);
		while(retorno == 0){ //&& check_visited_place(memory,memory_size,current_position)){
			if(ind[k].getNumGenes() > TAM_MIN){
				ind[k].DecreaseIndividual(2);
				path.pop();
				current_position = path.top();
			}else{
				current_position = path.top();
				retorno = check_unvisited_neighborhood(current_position,dim_map,memory,memory_size,map);
				printf("\nretorno: %d    current position: (%d,%d)   #genes: %d\n",retorno,current_position.x,current_position.y,ind[k].getNumGenes());
				print_path(memory,memory_size);
				//pera("retorno");
				//cout << "\n2 " << n++;
				//pera("dois");
				}
		}
		//pera("saiu");

	}


	//Increasing Individual chromossome
	if(is_in(current_position,dim_map) && !is_end_(end,current_position)){ //dentro do mapa
			ind[k].IncreaseIndividual(2);
			path = build_path(ind, k, start);
			current_position = path.top();

			while((check_visited_place(memory, memory_size, current_position) && !is_end_(end, current_position))){
					//|| !is_in(current_position, dim_map) || is_wall_(map,current_position)){ //garantindo que crie posicao valida que nunca foi visitada
				ind[k].DecreaseIndividual(2);
				path.pop();
				ind[k].IncreaseIndividual(2);
				path = build_path(ind, k, start);
				current_position = path.top();
				cout << "\n3 " << n++;
				//sleep(SLEEP_TIME);
				//pera("tres");
			}

	}
	else if(!is_in(current_position,dim_map)){ //fora do mapa
		if(ind[k].getNumGenes() > TAM_MIN){
			ind[k].DecreaseIndividual(2);
		}

		return 0;
	}

	if(memory) delete[] memory;
	//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



	//$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
	//construindo possivel solucao e
	//verificando a qualidade da "solucao"
	path = build_path(ind,k,start);
	current_position = path.top();


	Point *mypath;
	mypath = build_path_(path);

	int path_size = path.size();

	//print_path(mypath,path_size);
	//pera("path final");

	Point point_anterior = mypath[0],point_posterior = mypath[2];

	//double distancia = euclidian_distance_2D(current_position,end);


	int num_de_batidas = 0;
	for(int i=0;i<path_size;i++){
		//problema do vai e volta... penalizado qdo isso ocorre
		if(i >=i && i < path_size-1){
			point_anterior = mypath[i-1];
			point_posterior = mypath[i+1];
			if(point_anterior.x == point_posterior.x && point_anterior.y == point_posterior.y){
				fit = fit/(double)(PENALTY+1);
				//fit = fit - PENALTY;
			}
		}


		if (is_in(mypath[i],dim_map)) {
			if (!is_wall_(map, mypath[i])) {
				//fit = fit + 1/(double)ind[k].getNumGenes();
				fit = fit + BONUS + 1/(double)ind[k].getNumGenes();
				//fit = fit + BONUS;
				//fit = fit + 1/(double)ind[k].getNumGenes() - distancia;
				//fit = fit + 1/(double)ind[k].getNumGenes() - distancia + BONUS;
				//fit = fit + 1/(double)ind[k].getNumGenes() + BONUS/2;
			} else if (is_wall_(map, mypath[i])) {
				num_de_batidas++;
				//fit = fit - PENALTY;
				//fit = fit/(double)(PENALTY+1);
				//fit = fit/(double)(PENALTY+1) - PENALTY/2;
				//fit = fit/(double)(PENALTY) - PENALTY;
				//fit = fit/(double)(PENALTY) - num_de_batidas;
				fit = (fit/(double)(PENALTY+num_de_batidas)) - num_de_batidas;
				//if(ind[k].getNumGenes()-(i*2) >= 2)
					//ind[k].DecreaseIndividual(i*2);
				//if (mypath) delete[] mypath;
				//return 0;

			}
		}
		else{
			//cout << "\n" << mypath[i].x << "," << mypath[i].y << "\n";
			//pera("caminho fora do mapa");
			if(ind[k].getNumGenes()-(i*2) >= 2)
				ind[k].DecreaseIndividual(i*2);
			if (mypath) delete[] mypath;
			return 0;
		}
	}


	 if (is_end_(end, current_position) ){
		//fit = (fit+BONUS+1/(double)ind[k].getNumGenes());
		 fit = (fit+BONUS)*2 + 1/(double)ind[k].getNumGenes();
		return fit;
	 }

		if(mypath) delete[] mypath;


		//printf("\n%f\n",fit);
		//printf("\nFim Fitness\n");
	return fit;
	//$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
}
//---------------------------------------------------------------------------------------------------------------------------
string *load_map(FILE *fl, int *num_linhas_mapa){
    string *mapa;
    *num_linhas_mapa = count_lines(fl) - 1;
    int i_linha = 0;
    mapa = new string[*num_linhas_mapa];
    char line_temp[TAM_MAX_LINHA];
    rewind(fl);
    while(fgets(line_temp,TAM_MAX_LINHA,fl) != NULL){
        int z = 0;
        while(line_temp[z] != '\r' && line_temp[z] != '\n'){line_temp[z] = tolower(line_temp[z]); z++;}
        line_temp[z] = '\0';
        mapa[i_linha] = line_temp;
        i_linha++;
    }
    return mapa;
}
//------------------------------------------------------------------------------
//conta a quantidade de linhas do arquivo
int count_lines(FILE *fl){
    int linhas = 1;
    char c;
    rewind(fl);

    do{
         c = fgetc(fl);
         if(c == '\n')
           linhas++;

    }while(c != EOF);
    rewind(fl);
    return linhas;
}
//------------------------------------------------------------------------------
int **get_reduced_map(int **mapa,Point dim_map,Point *dim_reduced_map){
	int new_dimy = (dim_map.y+1)/2, **new_map;

	new_map = new int*[dim_map.x];
	for(int i=0;i < dim_map.x;i++)
		new_map[i] = new int[new_dimy];

	bool sequence3_0 = false;
	int cont;
	for(int i=0;i<dim_map.x;i++){
		cont = 0;
		sequence3_0 = false;
		for(int j=0;j<dim_map.y;j++){
			if(j<(dim_map.y-2)){
				if(mapa[i][j] == 9){
					new_map[i][cont] = 9;
					sequence3_0=false;
					//cont++;
				}
				else if(mapa[i][j] == 1 && mapa[i][j+1] == 1 && mapa[i][j+2] == 1){
					j = j+2;
					new_map[i][cont] = 1;
					//cont++;
				}
				else if(mapa[i][j] == 0 && mapa[i][j+1] == 0 && mapa[i][j+2] == 0 && sequence3_0==false){
					j = j+2;
					new_map[i][cont] = 0;
					sequence3_0 = true;
					//cont++;
				}
				else if(mapa[i][j] == 1){
					sequence3_0=false;
					new_map[i][cont] = 1;
					//cont++;
				}
				else if(mapa[i][j] == 0 && mapa[i][j+1] == 3 && mapa[i][j+2] == 0){
					j = j+2;
					new_map[i][cont] = 3;
					//cont++;
				}
				else if(mapa[i][j] == 0 && mapa[i][j+1] == 5 && mapa[i][j+2] == 0){
					j = j+2;
					new_map[i][cont] = 5;
				}
				/*else if(mapa[i][j] == 3 && mapa[i][j+1] == 0){
					j = j+2;
					new_map[i][cont] = 3;
					//cont++;
				}
				else if(mapa[i][j] == 5 && mapa[i][j+1] == 0){
					j = j+2;
					new_map[i][cont] = 5;
				}*/
				else if(mapa[i][j] == 0 && sequence3_0 == true){
					sequence3_0 = false;
					new_map[i][cont] = 0;
					//printf("\ninvalido!\n");
				}
				cont++;
			}
			else{
				if(mapa[i][j] == 5)
					new_map[i][cont] = 5;
				else if(mapa[i][j] == 3)
					new_map[i][cont] = 3;
				else{

				}
			}
		}
		new_map[i][new_dimy-1] = 9;
	}

	dim_reduced_map->x = dim_map.x;
	dim_reduced_map->y = new_dimy;

	return new_map;
}
//------------------------------------------------------------------------------
int **preProcessing(int **mapa,Point dim_map){
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(mapa[i][j] == 9)
				mapa[i][j] = 1;

	return mapa;
}
//------------------------------------------------------------------------------
int **copy_map(int **map,Point dim_map){
	int **copy;
	copy = new int*[dim_map.x];
	for(int i=0;i < dim_map.x;i++)
		copy[i] = new int[dim_map.y];

	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			copy[i][j] = map[i][j];

	return copy;
}
//------------------------------------------------------------------------------
void clone(int **origem,int **destino,Point dim_map){
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			destino[i][j] = origem[i][j];
}
//------------------------------------------------------------------------------
int get_number_of_valid_space(int **map, Point dim_map){
	int valid_space = 0;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(map[i][j] == 0)
				valid_space++;

	return valid_space;
}
//------------------------------------------------------------------------------
int **str_map2bin_map(string map[], int num_linhas,Point *dim_labirinto){
	int dimx, dimy;
	dimx = num_linhas;
	dimy = map[0].length(); //assume-se q todas as linhas possuem o mesmo tamanho...
	int **bin_map;
	//cout << dimy << endl; string x; cin >> x;

	//criando matriz dinamicamente
	bin_map = new int*[dimx];
	for(int i=0;i < dimx;i++)
		bin_map[i] = new int[dimy];

	char *temp = new char[dimy+1];

	for(int i=0;i < dimx;i++){
		strcpy(temp,map[i].c_str());
		for(int j=0;j < dimy;j++){
			if(temp[j] == ' ')
				bin_map[i][j] = 0;
			else if(temp[j] == 's')
				bin_map[i][j] = 5;
			else if(temp[j] == 'e')
				bin_map[i][j] = 3;
			else if(temp[j] == '+')
				bin_map[i][j] = 9;
			else
				bin_map[i][j] = 1;
		}
	}

	dim_labirinto->x = dimx;
	dim_labirinto->y = dimy;
	delete[] temp;

	return bin_map;
}
Point FindStartPoint(int **map,Point dim_map){
	Point start;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(map[i][j] == 5){
				start.x = i;
				start.y = j;
				return start;
			}

	return start;
}
//------------------------------------------------------------------------------
Point FindEndPoint(int **map,Point dim_map){
	Point end;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(map[i][j] == 3){
				end.x = i;
				end.y = j;
				return end;
			}

	return end;
}
//------------------------------------------------------------------------------
int count_good_genes(int **solution_map,int **map,Point dim_map){
	int count = 0;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(solution_map[i][j] == 4 && map[i][j] == 0)
				count++;

	return count*2;
}
//------------------------------------------------------------------------------
int count_erros(int **solution_map,int **map,Point dim_map){
	int count = 0;
	for(int i=0;i<dim_map.x;i++)
		for(int j=0;j<dim_map.y;j++)
			if(solution_map[i][j] == 4 && map[i][j] == 1)
				count++;

	return count;

}
//------------------------------------------------------------------------------
void printMapa(int **map,Point dim_map){
	printf("\n");
	for(int i=0;i<dim_map.x;i++){
		for(int j=0;j<dim_map.y;j++)
			printf("%d",map[i][j]);
		printf("\n");
	}
}
//------------------------------------------------------------------------------
int **InsertSolution(Individual *ind,int k,int **map,Point dim_map){
	Point current_point = FindStartPoint(map,dim_map);
	int g1,g2;
	//ind[k].printIndividual(); string x; cin >> x;
	for(int i=0;i<ind[k].getNumGenes()-1;i=i+2){
		g1 = ind[k].getGene(i);
		g2 = ind[k].getGene(i+1);
		//11 - norte
		if(g1 == 1 && g2 == 1){
			current_point.x = current_point.x - 1;
			if(is_in(current_point,dim_map)){
				map[current_point.x][current_point.y] = 4;
			}
			else{
				//printf("\nPasso para o Norte, fora do mapa\n");
			}
		}
		//00 - sul
		else if(g1 == 0 && g2 == 0){
			current_point.x = current_point.x + 1;
			if(is_in(current_point,dim_map)){
				map[current_point.x][current_point.y] = 4;
			}
			else{
				//printf("\nPasso para o Sul, fora do mapa\n");
			}
		}
		//01 - ateY,int k_tournament,int k_elitism,int max_min_type);leste
		else if(g1 == 0 && g2 == 1){
			current_point.y = current_point.y + 1;
			if(is_in(current_point,dim_map)){
				map[current_point.x][current_point.y] = 4;
			}
			else{
				//printf("\nPasso para o Leste, fora do mapa\n");
			}
		}
		//10 - oeste
		else if(g1 == 1 && g2 == 0){
			current_point.y = current_point.y - 1;
			if(is_in(current_point,dim_map)){
				map[current_point.x][current_point.y] = 4;
			}
			else{
				//printf("\nPasso para o Oeste, fora do mapa\n");
			}
		}
		else{
			printf("\nInsertion Solution, Error! Invalid Gene: (%d,%d)\n",g1,g2);
		}

	}

	return map;
}
//------------------------------------------------------------------------------
double euclidian_distance_2D(Point ponto1,Point ponto2){
	double distance = 0.0;

	distance = pow((ponto1.x - ponto2.x),2) + pow((ponto1.y - ponto2.y),2);

	return sqrt(distance);
}
//------------------------------------------------------------------------------
CImg<int> update_display(int **map,CImg<int> cimg_labirinto){
	cimg_forXY(cimg_labirinto,x,y){
		if(map[x][y] == 1) //wall
			cimg_labirinto(y,x,0) = cimg_labirinto(y,x,1) = cimg_labirinto(y,x,2) = 0;
		else if(map[x][y] == 0)//free space
			cimg_labirinto(y,x,0) = cimg_labirinto(y,x,1) = cimg_labirinto(y,x,2) = 255;
		else if(map[x][y] == 5){//start
			cimg_labirinto(y,x,0) = 255;
			cimg_labirinto(y,x,1) = 0;
			cimg_labirinto(y,x,2) = 0;
		}
		else if(map[x][y] == 3){//end
			cimg_labirinto(y,x,0) = 0;
			cimg_labirinto(y,x,1) = 255;
			cimg_labirinto(y,x,2) = 0;
		}
		else if(map[x][y] == 4){// caminho...
			cimg_labirinto(y,x,0) = 0;
			cimg_labirinto(y,x,1) = 0;
			cimg_labirinto(y,x,2) = 255;
		}
		else{
		}

	}

	return cimg_labirinto;
}
//---------------------------------------------------------------------------------------------------------------------------
bool is_wall(int **map,int x, int y){
	if(map[x][y] == 1)
			return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
bool is_wall_(int **map,Point current_position){
	if(map[current_position.x][current_position.y] == 1)
		return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
bool is_start(int **map,int x, int y){
	if(map[x][y] == 5)
		return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
bool is_end(int **map,int x, int y){
	if(map[x][y] == 3)
			return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
bool is_end_(Point end,Point current_position){
	if(end.x == current_position.x && end.y == current_position.y)
		return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
bool is_in(Point current_point, Point dim_map){
	if((current_point.x >= 0 && current_point.x < dim_map.x) && (current_point.y >= 0 && current_point.y < dim_map.y))
		return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
bool is_inside(int x,int y,Point dim_map){
	if((x >= 0 && x < dim_map.x) && (y >= 0 && y < dim_map.y))
		return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
bool check_north(Point cp,int **map,Point dim){
	if(is_inside(cp.x-1,cp.y,dim))
		if(!is_wall(map,cp.x-1,cp.y))
			return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
bool check_south(Point cp,int **map,Point dim){
	if(is_inside(cp.x+1,cp.y,dim))
		if(!is_wall(map,cp.x+1,cp.y))
			return true;

	return false;

}
//-------------------------------------------------------------------------------------------------------------
bool check_east(Point cp,int **map,Point dim){
	if(is_inside(cp.x,cp.y+1,dim))
		if(!is_wall(map,cp.x,cp.y+1))
			return true;

	return false;

}
//-------------------------------------------------------------------------------------------------------------
bool check_west(Point cp,int **map,Point dim){
	if(is_inside(cp.x,cp.y-1,dim))
		if(!is_wall(map,cp.x,cp.y-1))
			return true;

	return false;

}
//-------------------------------------------------------------------------------------------------------------
Point *build_memory(stack<Point> mystack){
	Point *memoria;
	int path_size = mystack.size();
	memoria = new Point[path_size];
	//inicializando com alguma coisa... pode ser a posicao corrente mesmo...
	for(int i=0;i<path_size;i++){
		memoria[i].x = memoria[i].y = 0;
	}


	//criando memoria
	int pop_count = 0;
	if(!mystack.empty()){
		for(int i=0;i<path_size;i++){
			if(!mystack.empty()){
				memoria[i] = mystack.top();
				mystack.pop(); //desempilhando
				pop_count++;
			}
		}
		//reempilhando
		for(int i=pop_count-1;i>=0;i--){
				mystack.push(memoria[i]);
		}
	}

	return memoria;

}
//-------------------------------------------------------------------------------------------------------------
bool check_visited_place(Point *places_keeped,int path_size,Point current_position){
	for(int i=0;i<path_size;i++)
		if(places_keeped[i].x == current_position.x && places_keeped[i].y == current_position.y)
			return true;

	return false;
}
//-------------------------------------------------------------------------------------------------------------
int check_unvisited_neighborhood(Point current_point,Point dim_map,Point *path,int path_size,int **map){
	Point backup_cp = current_point;
	int retorno = 0;
	/*
	 * retorno:
	 * 0 - so possui vizinhos fora do mapa ou nao possui vizinhos que nao foram visitados ou sao vizinhos paredes
	 * 1 - possui 1 vizinho nao visitado
	 * 2 - possui 2 vizinhos nao visitados
	 * 3 - possui 3 vizinhos nao visitados
	 * 4 - possui 4 vizinhos nao visitados
	 * */
	if(is_inside(current_point.x-1,current_point.y,dim_map)){ //norte
		current_point.x--;
		if(!check_visited_place(path,path_size,current_point) && !is_wall_(map,current_point)){
			retorno++;
		}
	}

	current_point = backup_cp;
	if(is_inside(current_point.x+1,current_point.y,dim_map)){ //sul
		current_point.x++;
		if(!check_visited_place(path,path_size,current_point) && !is_wall_(map,current_point)){
			retorno++;
		}
	}

	current_point = backup_cp;
	if(is_inside(current_point.x,current_point.y+1,dim_map)){ //leste
		current_point.y++;
		if(!check_visited_place(path,path_size,current_point) && !is_wall_(map,current_point)){
			retorno++;
		}
	}

	current_point = backup_cp;
	if(is_inside(current_point.x,current_point.y-1,dim_map)){ //oeste
		current_point.y--;
		if(!check_visited_place(path,path_size,current_point) && !is_wall_(map,current_point)){
			retorno++;
		}
	}


	return retorno;
}
//-------------------------------------------------------------------------------------------------------------
